#include <iostream>
#include <stdlib.h>     // Need random(), srandom()
#include <time.h>       // Need time()
#include <vector>       // Need vector
#include <algorithm>    // Need for_each()
#include <iterator>

using namespace std;
class Solution
{
public:
    static bool Find(int target, vector<vector<int>> array)
    {
        int rol = array.size();
        int col = array[0].size();
        if(rol == 0 || col == 0)
            return false;
        else
        {
            int colIndex = col;
            for(int i=0; i<rol; i++)
            {
                if(array[i][0] > target)
                    return false;
                for(int j=0; j<=colIndex; j++)
                {
                    if(array[i][j] == target)
                        return true;
                    else if(array[i][j] > target)
                    {
                        colIndex = j;
                        break;
                    }
                    else
                        continue;
                }
            }
        }
        return false;
    }
};

int main()
{
    vector<vector<int>> vi;
    int a[] = {1,2,8,9};
    vector<int> v1(begin(a),end(a));
    vi.push_back(v1);
    int b[] = {2,4,9,12};
    vector<int> v2(begin(b),end(b));
    vi.push_back(v2);
    int c[] = {4,7,10,13};
    vector<int> v3(begin(c),end(c));
    vi.push_back(v3);
    int d[] = {6,8,11,15};
    vector<int> v4(begin(d),end(d));
    vi.push_back(v4);
    cout<<Solution::Find(22,vi);
    return 0;
}
